Basic Explanation of Garbage Collection
Garbage collection is a complex topic that has been the subject of hundreds of technical articles and at least one text book. The following is a simplified explanation of dynamic memory allocation and garbage collection. For a more complete explanation of basic garbage collection technology, see U.S. Pat. No. 5,088,036, and Richard Jones and Rafael Lins, "Garbage Collection," John Wiley & Sons Ltd., 1996, both of which are incorporated by reference as background information.
Referring to FIG. 1, there is shown a typical multitasking computer system 100 that has a CPU 102, user interface 106, and memory 108 (including both fast random access memory and slower non-volatile memory). The memory 108 stores an operating system 110 and one or more mutator tasks 112 (also called processes or threads). Each active task in the system is assigned a portion of the computer's memory, including space for storing the application level code 112 executed by the task, space for storing a storing a program stack 114, and a heap 116 that is used for dynamic memory allocation.
The program stack 114 need not be in contiguous pages of memory 108, and if not contiguous, the pages or possibly larger contiguous chunks of stack storage are linked together using well known prior art mechanisms.
The CPU 102 includes an instruction cache 120 for providing instructions to an instruction decoder and execution logic 122. The CPU also includes a stack cache 124 for storing in high speed cache memory a portion of the program stack 114, and a set of registers 126 for storing data values, object references 128 and the like. The program stack 114, including the portion in the stack cache 124, is used to temporarily store various data structures and parameters, which including activation records (sometimes called "frames" ) that are pushed on the program stack each time a method or other procedure is invoked. Some of the data values pushed onto the program stack are object references 130.
During garbage collection, the program stack 114 and the registers 126 in the CPU 102 are typically used to locate a "root set" of object references or pointers used by the mutator task 112. A root set locator procedure in the garbage collector will typically generate and store a root set list 132 of the located root set object references.
It should be understood that FIG. 1 represents only one of many ways in which memory may be allocated for storing the roots, code and heap associated with a task or a set of tasks. Also, it should be understood that multiple processes may be executing simultaneously in a computer system, each with its own address space that includes the same types of items as shown in the memory 108 of FIG. 1.
For the purposes of this description, the terms "task", "mutator", "mutator thread", "thread" and "process" are used interchangeably. Tasks and programs are sometimes called mutators because they change or "mutate" the contents of the heap 116. The term "thread" relates to the continuity of a task or process, especially in multithreaded environments in which each process is periodically interrupted by other ones of the processes in the system.
The term "object" is herein defined to mean any data structure created by a program or process.
The terms "reference" and "object reference" are used interchangeably to describe a data structure that includes a pointer to an object. While the term "pointer" or "object pointer" are sometimes used interchangeably with "reference" and "object reference", object references may include information in addition to a pointer. An object reference may be direct or indirect. A direct object reference directly points to an object header, while an indirect object reference points to an object handle. In this document the term "object reference" refers to both types. While in the preferred embodiment object handles are not shown, the present invention is equally applicable to systems in which object handles are used.
The terms "write" and "store" are used interchangeably in this document to refer to the operation in which data is stored at a specified location in a computer's memory, or in a register. The terms "write operation" and "store operation" are also used interchangeably.
The term "target object" is used to mean the object into which a datum is being written or from which a datum is being read. Equivalently, the target object is the one referenced by an object reference.
The terms "object reference write instruction" is used to refer to an instruction that uses an object reference to locate an object into which a datum is to be written. The object reference used by the write operation to locate the object is sometimes called the target object reference.
The terms "instruction execution logic" and "the hardware" refer to all the internal logic in a microprocessor such as its instruction pipeline, any load and store buffers, state machines, microcoded execution logic, stack management logic, and so on, that may be needed to completely fetch and execute an instruction from an instruction cache.
The terms "state flag," "state bit," "S flag," and "S bit" are used interchangeably to refer to the flag or bit in an object reference and in the object header in the preferred embodiment of the present invention. When a distinction between locations of the state flags needs to be made the terms "object reference state flag" and "object header state flag" are used. This flag or bit indicates that an associated object has been "stored into" or is "dirty" or has been "accessed" or "touched, to indicate that the object has been written into, or read from, by the mutator thread between the last garbage collection cycle in which this object was examined and the next such garbage collection cycle. For garbage collectors that use read or write barrier operations to trigger a garbage collection method specific recording operation when the object pointed to by an object reference is written to or read from, the state flag also acts as a filter to avoid triggering the read or write barrier operations once the state flag is set. The object reference state flag may be set by hardware, or the software within the read or write barrier procedure, but it is examined in hardware. In a second embodiment, in which the state flag is used as a "dirty" or "accessed" bit, the object reference state flag is only set in the hardware on an object reference write or read instruction, but is examined by garbage collection software. In a third embodiment, the above discussed operations are performed directly on the object header state flag by the instruction execution logic hardware instead of being performed on an object reference state flag.
When the task associated with the heap 116 needs space for storing an array or other program "object", a Memory Allocator routine 140 in the operating system is called. The memory allocator 140 responds by allocating a block of unused memory in the heap 116 to the task. Additional requests for memory will result in the allocation of additional memory blocks. Clearly, if the task continues to ask for more memory, all the space in the heap 116 will eventually be used and the task will fail for lack of memory. Therefore space must be restored by either explicit actions of the program, or some other mechanism.
It is well known that most tasks "abandon" much of the memory space that is allocated to them. Typically, the task stores many program objects in allocated memory blocks, and discards all references to many of those objects after it has finished processing them because it will never need to access those objects again.
An object for which there are no references (sometimes called pointers) is often termed an "inaccessible object", and the memory space it occupies is "inaccessible" to the task that once used it.
The solution to this problem is to recover blocks of memory space in the heap 116 that are no longer being used by the task. Garbage collection is the term used to refer to automatic methods of recovering unused memory in the heap 116. Garbage collector 142 generally gathers and recovers unused memory upon the occurrence of a predefined event, such as the expiration of a predefined time period, or usage of a certain amount of the available heap. Thus, FIG. 1 shows that the operation system 110 includes a garbage collector 142.
Thus, the purpose of the garbage collector 142 is to recover unused or abandoned portions of memory in the heap 116 so that the task using the heap will not run out of memory.
While there are a number of different garbage collection methodologies, the easiest one to explain is the Stop and Copy garbage collection technique. In this scheme the heap is divided into two halves, also called semi-spaces, and the program uses only one semi-space at a time. Stop and Copy garbage collectors reclaim unused memory and compact the program accessible memory used by a task by copying all "accessible objects" in the current semi-space to a contiguous block of memory in the other semi-space, and changing all references to the accessible objects so as to point to the new copy of these objects. An accessible object is any object (i.e., block of memory) that is referenced, directly or indirectly, by the "roots" or "root set" of the task. Typically, the "root set" of a task with respect to garbage collection is a set of object references stored in known locations, in the program stack 114 and registers 126 used by the task, which point to objects used by a task. Many of those objects, in turn, will contain references to other objects used by the task. The chain, or directed graph, of object references emanating from the root set indirectly points to all of the accessible objects in the heap.
The entire set of objects referenced by these object references (pointers) is called the set of accessible objects. Inaccessible objects are all objects not referenced by the set of object references derived from the root set.
By copying all accessible objects to a new contiguous block of memory in the heap, and then using the new copy of the objects in place of the old copy, the Stop and Copy garbage collector eliminates all unused memory blocks in the heap. It also "compacts" the memory storage used by the task so that there are no "holes" between accessible objects. Compaction is a desirable property because it puts all of the memory available for allocation to a task in a contiguous block, which eliminates the need to keep track of numerous small blocks of unallocated memory. Compaction also improves virtual memory performance.
Also shown in FIG. 1 are aspects of a computer system that is set up to execute "Java" (a trademark of Sun Microsystems, Inc.) bytecode programs. In particular, the operating system of such a system includes:
a bytecode program verifier 144 for verifying whether or not a specified Java bytecode program satisfies certain predefined integrity criteria; PA1 a class loader 146, which loads object classes into a user's address space and utilizes the bytecode program verifier 144 to verify the integrity of the methods associated with each loaded object class; and PA1 a bytecode program interpreter (not shown) for executing Java bytecode programs. If the instruction decoder and execution logic 122 is designed to execute Java bytecode instructions, a bytecode program interpreter is not needed.
Furthermore, in a computer system set up to execute Java bytecode programs, memory 108 will include at least one class repository 150, for locally storing object classes 152 in use and/or available for use by users of the computer system 100. The heap 116 acts as an object repository for storing objects, which are instances of objects of the object classes stored in the class repository 150.
When a computer system supports multithreading, it is possible for two or more threads of execution to share a single address space. In such systems, each thread of execution is typically considered to be a separate mutator task, and each has its own stack and register set.
Referring to FIG. 2, there is shown a conventional object 153 and an object reference 154 that includes a pointer 155 to the object 153. For purposes of this explanation, it is assumed that the computer system in which the object 153 and object reference 153 are stored has a word size of 32 or 64 bits, that each object reference includes a number of unused bits 156, 157. Each object 153 includes a header 158 and a body 159. The contents of the object header 150 are controlled by the operating system and are generally not accessible to users and application programs. The object body 159 is the part of the object that is visible to application programs.
While FIG. 2 shows an object reference pointing directly to an object body, the subsequent discussion is also applicable when the object reference points to an object via an object handle. Also, while the object header is shown in FIG. 2 as being located next to the object body, it can be located anywhere, including in an object handle where present.
For the purposes of this document, only one part of the object header 158 is of interest. In systems using "generational garbage collection", the header 158 of each object may include garbage collection information (gc info) 148. In particular, the gc info 148 in the object header 158 may indicate (A) the heap generation in which the object is stored, and (B) a state flag 149, the use of which will be described next.